import { defaultToString } from '../util';
import { ValuePair } from './models/value-pair';
/**
 * HashTable：Dictionary类的一种散列表实现，也叫HashMap。区别就是HashTable用hash值作为键，并且可以相同key不同value
 * 线性探查法将每个元素都存储在表中，而不是借助链表等外物来解决冲突。当想向表中某个位置添加一个新元素的时候，
 * 如果索引为index的位置已经被占据了，就尝试index+1的位置，如果这个位置也被占据就尝试下一个直至找到空闲的位置
 * 要注意的是：在删除的时候我们会将下面的往上移，保证每个位置是连续的，而不是像hash-table-linear-probing-lazy
 * 用一个isDeleted来记录删除状态（懒删除），我们要真正的删除对应的元素
 */

export default class HashTableLinearProbingy<K, V> {
    private _toStrFn: (key: K) => string;
    private _table: { [key: string]: ValuePair<K, V> };
    constructor(toStrFn: (key: K) => string = defaultToString) {
        this._table = {};
        this._toStrFn = toStrFn;
    }
    /**
     * 散列函数1
     */
    private loseloseHashCode(key: K): number {
        if (typeof key === 'number') {
            return key;
        }
        const tableKey = this._toStrFn(key);
        let hash = 0;
        for (let i = 0, le = tableKey.length; i < le; i ++) {
            hash += tableKey.charCodeAt(i);
        }
        return hash % 37;
    }
    /**
     * 散列函数2
     * 一个表现良好的散列函数由几个方面构成：
     * 插入和检索元素的时间（即性能），以及较低的冲突可能性。
     */
    /* private djb2HashCode(key: K) {
        const tableKey = this._toStrFn(key);
        let hash = 5381;
        for (let i = 0; i < tableKey.length; i ++) {
            hash = (hash * 33) + tableKey.charCodeAt(i);
        }
        return hash % 1013;
    } */
    /**
     * 得到key对应的hash值，这个hash值会作为hashtable的键
     */
    public hashCode(key: K): number {
        // return this.djb2HashCode(key); // 使用更好的散列函数
        return this.loseloseHashCode(key);
    }
    /**
     * 向HashTable中添加新元素。当想向表中某个位置添加一个新元素的时候，如果索引为index的位置
     * 已经被占据了，就尝试index+1的位置，如果这个位置也被占据就尝试下一个直至找到空闲的位置
     */
    public put(key: K, value: V): boolean {
        if (key != null && value != null) {
            const tableKey: number = this.hashCode(key);
            // 这个位置没有被用过，就可以插入新元素
            if (this._table[tableKey] == null) {
                this._table[tableKey] = new ValuePair<K, V>(key, value);
            } else { // 需要向下一个位置进发
                let index: number = tableKey + 1;
                // 该位置被占了，那就找出下一个可用的位置
                while (this._table[index] != null) {
                    index ++;
                }
                this._table[index] = new ValuePair<K, V>(key, value);
            }
            return true;
        }
        return false;
    }
    /**
     * 通过以键值作为参数查找对应的值并返回
     */
    public get(key: K): V {
        if (key == null) { // 参数不合法
            return undefined;
        }
        const tableKey: number = this.hashCode(key);
        if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回undefined
            return undefined;
        }
        if (this._table[tableKey].key === key) {
            return this._table[tableKey].value;
        } else {
            let index: number = tableKey + 1;
            while (this._table[index] != null && this._table[index].key !== key) {
                index ++;
            }
            return this._table[index] != null ? this._table[index].value : undefined;
        }
    }
    /**
     * 通过键来删除字典中对应的键值对
     */
    public remove(key: K): boolean {
        if (key == null) { // 参数不合法
            return false;
        }
        const tableKey: number = this.hashCode(key);
        if (this._table[tableKey] == null) { // 因为是线性，这个为空证明下面的也没有，直接返回undefined
            return false;
        }
        if (this._table[tableKey].key === key) {
            delete this._table[tableKey];
            this.verifyRemoveSideEffect(key, tableKey);
            return true;
        } else {
            let index: number = tableKey + 1;
            while (this._table[index] != null && this._table[index].key !== key) {
                index ++;
            }
            if (this._table[index] != null) {
                delete this._table[index];
                this.verifyRemoveSideEffect(key, index);
                return true;
            }
            return false;
        }
    }
    /**
     * 如果HashTable后面有小于等于被删除key的hash值，先将这移到空缺处，
     * 然后继续向后遍历，当前位置的hash值小于等于空缺处的hash值，就将这移到空缺处，
     * 总之就是在遍历一遍的情况下尽可能的保证hash值有序，可能会存在个别无序或者还有空缺的地方
     * @param key 键
     * @param removedPosition 删除时的位置的散列值（hash值）
     */
    private verifyRemoveSideEffect(key: K, removedPosition: number) {
        const hash = this.hashCode(key);
        let index = removedPosition + 1;
        while (this._table[index] != null) {
            const posHash = this.hashCode(this._table[index].key);
            if (posHash <= hash || posHash <= removedPosition) {
                this._table[removedPosition] = this._table[index];
                delete this._table[index];
                removedPosition = index;
            }
            index++;
        }
    }
    /**
     * hashtable大小
     */
    public size(): number {
        return Object.keys(this._table).length;
    }
    /**
     * hashtable是否为空
     */
    public isEmpty(): boolean {
        return this.size() === 0;
    }
    /**
     * 返回hashtable
     */
    public getTable(): { [key: string]: ValuePair<K, V> } {
        return this._table;
    }
    /**
     * 清空hashtable
     */
    public clear() {
        this._table = {};
    }
    /**
     * 返回hashtable的字符串形式
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        const keys = Object.keys(this._table);
        let objString = `{${keys[0].toString()} => ${this._table[keys[0]].toString()}}`;
        for (let i = 1; i < keys.length; i ++) {
            objString = `${objString},{${keys[i].toString()} => ${this._table[keys[i]].toString()}}`;
        }
        return objString;
    }
}
